/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<vector<int>> direct = {{1,0},{-1,0},{0,1},{0,-1}};
    bool dfs(vector<vector<char>>& board, string word,int pos,int path_i,int path_j,vector<vector<int>>& visited) {
        if(board[path_i][path_j] != word[pos]) {//剪枝条件
            return false;
        }
        if(pos == word.length()-1) {//终止条件
            return true;
        }
        visited[path_i][path_j] = 1;
        bool result = false;
        for(int i = 0;i < direct.size();i++) {
            int new_i = path_i + direct[i][0];
            int new_j = path_j + direct[i][1];
            if(new_i >= 0 && new_i < board.size() && new_j >= 0 && new_j < board[0].size()) {
                if(!visited[new_i][new_j]) {
                    bool flag = dfs(board,word,pos + 1,new_i,new_j,visited);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[path_i][path_j] = 0;
        return result;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size(), w = board[0].size();
        vector<vector<int>> visited(h, vector<int>(w));
        for(int i = 0;i < board.size();i++) {
            for(int j = 0;j < board[0].size();j++) {
                if(board[i][j] == word[0]) {
                    bool flag = dfs(board,word,0,i,j,visited);
                    if(flag) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};
// @lc code=end

